class AVLNode {
    constructor(key, value) {
        this.key = key;
        this.value = value;
        this.left = null;
        this.right = null;
        this.height = 1; // 新节点的高度为1
    }
}

class AVLTree {
    constructor() {
        this.root = null;
    }
    
    // 获取节点高度
    getHeight(node) {
        return node ? node.height : 0;
    }
    
    // 获取平衡因子
    getBalanceFactor(node) {
        if (!node) return 0;
        return this.getHeight(node.left) - this.getHeight(node.right);
    }
    
    // 更新节点高度
    updateHeight(node) {
        if (!node) return;
        node.height = Math.max(this.getHeight(node.left), this.getHeight(node.right)) + 1;
    }
    
    // 右旋操作（针对LL情况）
    rightRotate(y) {
        const x = y.left;
        const T2 = x.right;
        
        // 执行旋转
        x.right = y;
        y.left = T2;
        
        // 更新高度
        this.updateHeight(y);
        this.updateHeight(x);
        
        return x; // 返回新的根节点
    }
    
    // 左旋操作（针对RR情况）
    leftRotate(x) {
        const y = x.right;
        const T2 = y.left;
        
        // 执行旋转
        y.left = x;
        x.right = T2;
        
        // 更新高度
        this.updateHeight(x);
        this.updateHeight(y);
        
        return y; // 返回新的根节点
    }
    
    // 插入操作的辅助方法（递归）
    _insert(node, key, value) {
        if (!node) return new AVLNode(key, value);
        
        if (key < node.key) {
            node.left = this._insert(node.left, key, value);
        } else if (key > node.key) {
            node.right = this._insert(node.right, key, value);
        } else {
            // 键已存在，更新值
            node.value = value;
            return node;
        }
        
        // 更新当前节点高度
        this.updateHeight(node);
        
        // 检查并恢复平衡
        return this._balance(node);
    }
    
    // 插入操作
    insert(key, value) {
        this.root = this._insert(this.root, key, value);
    }
    
    // 平衡操作（处理四种不平衡情况）
    _balance(node) {
        const balanceFactor = this.getBalanceFactor(node);
        
        // LL情况（左子树太高，且左子树的左子树更高）
        if (balanceFactor > 1 && this.getBalanceFactor(node.left) >= 0) {
            return this.rightRotate(node);
        }
        
        // RR情况（右子树太高，且右子树的右子树更高）
        if (balanceFactor < -1 && this.getBalanceFactor(node.right) <= 0) {
            return this.leftRotate(node);
        }
        
        // LR情况（左子树太高，但左子树的右子树更高）
        if (balanceFactor > 1 && this.getBalanceFactor(node.left) < 0) {
            node.left = this.leftRotate(node.left);
            return this.rightRotate(node);
        }
        
        // RL情况（右子树太高，但右子树的左子树更高）
        if (balanceFactor < -1 && this.getBalanceFactor(node.right) > 0) {
            node.right = this.rightRotate(node.right);
            return this.leftRotate(node);
        }
        
        return node; // 如果平衡，直接返回
    }
    
    // 删除操作的辅助方法
    _delete(node, key) {
        if (!node) return null;
        
        if (key < node.key) {
            node.left = this._delete(node.left, key);
        } else if (key > node.key) {
            node.right = this._delete(node.right, key);
        } else {
            // 找到要删除的节点
            
            // 情况1：没有子节点或只有一个子节点
            if (!node.left || !node.right) {
                const temp = node.left || node.right;
                node = temp || null;
            } else {
                // 情况2：有两个子节点，找到中序遍历后继节点
                const temp = this._minValueNode(node.right);
                node.key = temp.key;
                node.value = temp.value;
                node.right = this._delete(node.right, temp.key);
            }
        }
        
        if (!node) return null; // 如果树为空，直接返回
        
        // 更新高度并平衡
        this.updateHeight(node);
        return this._balance(node);
    }
    
    // 删除操作
    delete(key) {
        this.root = this._delete(this.root, key);
    }
    
    // 找到最小值的节点
    _minValueNode(node) {
        let current = node;
        while (current && current.left) {
            current = current.left;
        }
        return current;
    }
    
    // 前序遍历的辅助方法
    _preOrder(node, result = []) {
        if (node) {
            result.push({ key: node.key, value: node.value, height: node.height });
            this._preOrder(node.left, result);
            this._preOrder(node.right, result);
        }
        return result;
    }
    
    // 前序遍历
    preOrder() {
        return this._preOrder(this.root);
    }
    
    // 查找操作的辅助方法
    _search(node, key) {
        if (!node) return null;
        if (key === node.key) return node.value;
        if (key < node.key) return this._search(node.left, key);
        return this._search(node.right, key);
    }
    
    // 查找操作
    search(key) {
        return this._search(this.root, key);
    }
    
    // 判断树是否为空
    isEmpty() {
        return this.root === null;
    }
    
    // 获取树的高度
    getTreeHeight() {
        return this.getHeight(this.root);
    }
    
    // 中序遍历（用于排序输出）
    inOrder() {
        return this._inOrder(this.root);
    }
    
    _inOrder(node, result = []) {
        if (node) {
            this._inOrder(node.left, result);
            result.push({ key: node.key, value: node.value });
            this._inOrder(node.right, result);
        }
        return result;
    }
}

// 测试代码
function testAVLTree() {
    const avlTree = new AVLTree();
    
    console.log("=== 测试AVL树插入操作 ===");
    
    // 测试插入
    avlTree.insert(10, "A");
    avlTree.insert(20, "B");
    avlTree.insert(30, "C"); // 这里应该触发RR旋转
    console.log("插入10,20,30后的前序遍历:", avlTree.preOrder());
    
    avlTree.insert(5, "D");
    avlTree.insert(15, "E");
    console.log("再插入5,15后的前序遍历:", avlTree.preOrder());
    
    avlTree.insert(25, "F"); // 这里可能触发RL旋转
    console.log("插入25后的前序遍历:", avlTree.preOrder());
    
    // 测试查找
    console.log("\n=== 测试查找操作 ===");
    console.log("查找键10:", avlTree.search(10));
    console.log("查找键30:", avlTree.search(30));
    console.log("查找键99（不存在）:", avlTree.search(99));
    
    // 测试删除
    console.log("\n=== 测试删除操作 ===");
    avlTree.delete(15); // 删除叶子节点
    console.log("删除15后的前序遍历:", avlTree.preOrder());
    
    avlTree.delete(20); // 删除有两个子节点的节点
    console.log("删除20后的前序遍历:", avlTree.preOrder());
    
    avlTree.delete(10); // 删除根节点
    console.log("删除10后的前序遍历:", avlTree.preOrder());
    
    console.log("\n最终树结构验证:");
    console.log("查找键5:", avlTree.search(5));
    console.log("查找键25:", avlTree.search(25));
    console.log("查找键30:", avlTree.search(30));
}

// 运行测试
// testAVLTree();

// 综合演示函数
function demoAVLTree() {
    console.log("=== AVL树综合演示 ===");
    const avlTree = new AVLTree();
    
    console.log("初始状态 - 树是否为空:", avlTree.isEmpty());
    
    // 批量插入数据
    const data = [
        {key: 50, value: "Apple"},
        {key: 30, value: "Banana"},
        {key: 70, value: "Cherry"},
        {key: 20, value: "Date"},
        {key: 40, value: "Elderberry"},
        {key: 60, value: "Fig"},
        {key: 80, value: "Grape"}
    ];
    
    data.forEach(item => avlTree.insert(item.key, item.value));
    
    console.log("\n插入数据后:");
    console.log("树高度:", avlTree.getTreeHeight());
    console.log("前序遍历（显示高度）:", avlTree.preOrder());
    console.log("中序遍历（按键排序）:", avlTree.inOrder());
    
    // 测试查找
    console.log("\n查找测试:");
    console.log("查找键40:", avlTree.search(40));
    console.log("查找键100（不存在）:", avlTree.search(100));
    
    // 测试删除
    console.log("\n删除键30:");
    avlTree.delete(30);
    console.log("删除后前序遍历:", avlTree.preOrder());
    console.log("删除后树高度:", avlTree.getTreeHeight());
    
    console.log("\n最终状态 - 树是否为空:", avlTree.isEmpty());
}

// 运行演示
// demoAVLTree();

/*
 * AVL树实现总结：
 * 1. 节点结构：包含key, value, left, right, height
 * 2. 核心操作：插入、删除、查找
 * 3. 平衡机制：四种旋转操作（LL, RR, LR, RL）
 * 4. 时间复杂度：所有操作都是O(log n)
 * 5. 特点：自平衡二叉搜索树，保证树高度平衡
 */

// 导出类供其他模块使用
module.exports = { AVLTree, AVLNode };